Time division multiplexing (TDM) is a standard technique for aggregating independent data channels.
FIG. 1 shows a graphical view of aligned TDM channels for links A, . . . , n ready for switching. In a TDM channel, data is multiplexed (or muxed) according to location in time. Each port in a system must be aligned to some signal. In SONET, the alignment signal is an 8 kHz clock and start of frame. A stream within a channel is identified by its offset from the signal, with individual datum recurring every G clock ticks. The grainsize G defines the granularity of switching possible in a particular TDM system. In FIG. 1, each stream is labelled with a subscript to identify byte ordering within individual data channels.
FIG. 2 shows a graphical view of one of the problems associated with TDM switching. In general, a switch can be any number of inputs to any number of outputs. For simplicity, only switches of the same number of input and output ports are considered in this discussion but the concepts can be easily extended to asymmetrical switches of various numbers of input and output ports. Similarly, switches are often homogenous in terms of grain size, but grain size also may vary per port. In any case, the switch must perform buffering necessary to align data, and typically the buffering is related to the grainsize. In FIG. 2, bytes are labelled with a letter representing the input port and a number representing the byte position at the port. As can be seen in the output streams, bytes may be reordered to any position within a grain group, may be multicast to several ports (or a single port), and bytes may be dropped.
There are many known techniques for TDM switch architectures having different capabilities and costs. Perhaps the most obvious switch capable of connecting N input ports with N output ports is an N×N crossbar of internal switches or crosspoints. Given such a switching matrix, any output can be connected to any input through the setting of a single crosspoint switch regardless of other traffic on the switch. As N grows large, however, the number of internal switches becomes impractical since the number of internal switches is equal to the square of the number of inputs, and the number of inputs is the product of the number of ports times the grainsize. This style of switch is commonly referred to as an n2 architecture or a memory switch.
FIG. 3 shows an n2 architecture of a four-port crossbar switch. The blackened crosspoints of FIG. 3 represent switches set to connect data between horizontal and vertical wires. The rule for switch settings is that any row may have zero or more crosspoints set, but a column can set at most one crosspoint. Other n2 architectures include multiplexers, or muxes, to select from all inputs at each output. The key to an n2 architecture is that all outputs are available to all inputs, and this availability can only be provided by a cost based on the multiplicative product of the inputs and the outputs.
Charles Clos showed how an N port switch can be constructed as a three-stage network of smaller switches with substantially less cost than an n2 architecture. This can be seen, for example, in C. Clos “A Study of Non-blocking Switching Networks”, The Bell System Technical Journal, 1953, vol. 32, no. 2, pp. 406-424. A Clos network that is defined or described as v(m, n, r) has r switches of size n×m in stage 1, m switches of size r×r in stage 2, and r switches of size m×n in stage 3. When m=n, a rearrangeably non-blocking unicast network results where an algorithm is required to calculate switch settings and existing connections may need to be moved to make room for a new connection request Clos proved that when m≧2n−1, the resulting network does not require rearranging to satisfy any unicast request regardless of previous state, e.g. the network is strictly non-blocking for unicast. The cost of a Clos network measured in crosspoints is 2 rmn+mr2 compared to n2r2 for a memory switch.
FIG. 4 shows an example Clos switch with n=m=r=4. If each of the 4×4 switches in the network is implemented as a crossbar architecture of 16 crosspoints, then the total number of crosspoints required by the network is 12*16 or 192 as predicted by the cost equation for Clos switches compared to the 256 required by the n2 architecture. As the number of inputs grows, the hardware cost savings provided by the Clos network becomes more dramatic.
While unicast switches are useful, many applications require multicast. Active research has determined how much speedup is required to support multicast in crosspoint-reduced networks like Clos networks. Using reasoning similar to the proof of non-blocking unicast for Clos networks with 2× speedup and defining multicast as a single input being multicast to at most w outputs, then a Clos network with m=(w+1)n−w+1 will provide a strictly non-blocking switch supporting w-wide multicast.
With respect to terms used in this description, “blocking” occurs when a connection is made that can exclude the possibility of certain other connections being made. A switch is said to be “non-blocking” if any new connection request within the capacity of all input and output ports can be satisfied by the switch. A switch is said to be “wide sense non-blocking” when a particular connection rule must be applied in order to achieve a state in which a new connection can always be made. A switch is said to be “strict sense non-blocking” or “strictly non-blocking” when any connection rule can be applied to achieve a state in which a new connection can always be made without disturbing the existing connections. A switch is said to be “rearrangeably non-blocking” when a new connection can be made, but it might be necessary to reconfigure some other connections on the switch.
Given speedup of m=(w+1)n−w+1 within a Clos network and regardless of previously scheduled traffic, there is always capacity to schedule a connection between any set of outputs and an input assuming sufficient bandwidth at inputs and outputs. However, there is no guarantee even with this speedup that an existing multicast connection can have an arbitrary leaf added without rearrangement. A “leaf” is a terminal or bottom item of a tree, i.e., an item with no child; more formally, a leaf is a vertex with degree one, and can also be referred to as an external node, or as a terminal node. Even with the increased speedup, it may be necessary to delete and re-add the entire multicast connection in order to add a single leaf to the connection.
FIG. 5 shows an example Space:Time:Space switch. This switch has four ports A-D of four timeslots (e.g. n=4 and G=4). The input muxes 10 implement a space switch capable of writing one of the concurrently arriving bytes from any port into receiving, or “ping”, RAMs 20. A receiving RAM 20 can write the data into any timeslot (byte location) but can only receive one byte at a time. For this reason, the receiving RAM 20 cannot receive data from two different ports arriving at the same time. When an entire grain group, G bytes from each port, has been received, the data is shifted into output, or pong, RAMs 30 to be read for output. Output muxes 40 (similar to the input muxes 10) feed the output ports and similar rules apply in that any output port can receive only one-byte at a time although each can receive a byte from any of the pong RAMs. Ping and pong RAMs 20 and 30 can be implemented in a variety of ways: for example, an additional selector on the mux can choose between the two sets of RAMs, and in that case whether a particular RAM is acting as a ping RAM or a pong RAM depends on the current setting of that selector. Two such sets of RAM are typically required since a byte of the following grain group may arrive before the previous grain group's contribution has been read out. This would happen, for example, with succeeding bytes of the D1 stream, since the arriving D1 byte of a following grain group would overwrite the preceding byte without the dual RAMs.
Switches like the Space:Time:Space example of FIG. 5 are equivalent to Clos networks. In fact, the switches of FIG. 4 and FIG. 5 are equivalent. The translation from a Space:Time:Space switch to a Clos network is achieved by: creating independent first stage switches to switch each column of data arriving at the Space:Time:Space switch; implementing center stage switches capable of doing the time rearrangement of the RAM writes and reads; and finally by providing output switches for each of the columns of output created by the Space:Time:Space output muxes. The Space:Time:Space network makes use of the arrival and departure time of bytes to reuse the muxes for each of the 4×4 switches pictured in the Clos network.
The Space:Time:Space switch of FIG. 5 has minimal internal buffering, or zero speedup, is rearrangeably non-blocking for unicast, and requires an algorithm to calculate grain placement in memory. The acceptance of a new call may require changing the placement of existing calls in the RAM (and therefore also changing the mux settings). The scheduling state of this switch may be captured in a data structure that describes the input and output requirements of each RAM.
Let a connection be described by the form Label:(Input Streams→Output Streams) or for example 1:(A1−B2,C3) indicating that connection 1 connects the input of port A grain 1 to output port B grain 2 and output port C grain 3. If this connection were scheduled for RAM #1 at time 1, this could be pictured as shown in FIG. 6, which illustrates a schedule of RAM #1 with connection 1:(A1→B2,C3). In the figure, the labels 1 through 4 across the top represent the arrival timeslots of the input. The labels 1 through 4 on the bottom represent the output departure times. Since the RAM is capable of receiving an input grain from any port, only the grain arrival time needs to be considered for scheduling. The call number that annotates the path from 1 to 2 and 3 can be used to determine the mux selector setting. The figure shows that RAM #1 is free to receive another input in timeslots 2, 3 and 4, and is capable of delivering other outputs in timeslots 1 and 4.
A property of such switches for unicast traffic only is that in any two RAMs where an input grain is unassigned in one RAM and an output is unassigned in the other RAM, the two RAM schedules can be rearranged to admit a connection between the input and output. FIG. 7A shows an initial scheduling of RAM #1 and RAM #2. In FIG. 7B, the previous scheduling of RAMs #1 and #2 of FIG. 7A are rearranged to allow a new connection 3. In other words, FIG. 7B illustrates the rearrangement required to add 3:(C1→D1) to the previous scheduling shown in FIG. 7A. Algorithms guaranteed to succeed in such rearrangement can be found in the prior art, such as in J. Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, 1990, Chapter 3, pp. 53-84.
Multicast significantly complicates connection scheduling for two reasons: first, some loads are inherently blocking and can not be scheduled; second, even when the capability to carry the multicast exists, the problem of efficiently finding the schedule is NP hard or currently believed to require time exponential in the size of the input and is only practical for small switches. A problem is described with respect to computational complexity as being “NP hard” if solving it in polynomial time would make it possible to solve all problems in class NP (nondeterministic polynomial time) in polynomial time.
To see why Space:Time:Space switches and equivalent Clos networks are blocking for multicast, consider the connection requests of 1:(A1→A1,B2), 2:(B1→B1,C3), 3:(C1→B2,A3), 4:(D1→A2,C1) and 5:(A2→D1,B3). The scheduling of the first four requests, which are conflicting multicast connections, is shown in FIG. 8. It is impossible to schedule connection 5 in a single RAM since the new connection's outputs conflict with every other connection, and other traffic arriving in grain 2 make it impossible to multicast connection 5 through the input stage muxes.
Multicast capability is typically provided to switches of this kind through additional switch capacity. For example, a fifth RAM would provide capacity for scheduling connection 5 from the example above. Such additional capacity is called “speedup”. Sufficient speedup can change a rearrangeably non-blocking switch for unicast to a strictly non-blocking switch for unicast, and even greater speedup will make a switch strictly non-blocking for various widths of multicast.
To see why, consider a Space:Time:Space switch with 2n−1 RAMs and imagine scheduling the last connection of a 100% unicast load. There are n−1 RAMs receiving inputs at that grain time since there are n ports in the system. Likewise there are n−1 RAMs being read for output at the output grain time. If there is no overlap between the two sets of RAMs, then 2n−2 RAMs are unable to schedule this last connection, but this leaves at least one RAM guaranteed to be unscheduled for both the input and output grain. Therefore, with 2n−1 RAMs a Space:Time:Space switch is strictly non-blocking for unicast and will never require rearrangement. This is Clos's standard result for Clos networks applied to the RAM implementation of Space:Time:Space switches like that of FIG. 5.
Similarly, consider scheduling another 100% load comprised of both unicast and 2-cast connections and consider the last connection, a 2-cast request. In this case, at most n−1 RAMs can be receiving inputs. The hard case for the outputs is to assume different delivery times since a single delivery time could be serviced by a single RAM location. Therefore, assuming different delivery times for the outputs, n−1 RAMs may be delivering to the first output time and a second set of n−1 RAMs may be delivering to the second output time. If there is no overlap between the outputs and input, then as many as 3n−3 RAMs may be unavailable to schedule the request. This means that a switch with speedup of 3n−2 is sufficient for strictly non-blocking unicast and 2-cast. More generally, wn+n−w−1 speedup is sufficient for a non-rearrangeably non-blocking switch where w is the maximum width of multicast and n is the number of ports. Non-rearranging switches significantly simplify switch control. Rearranging switches require careful coordination to ensure no loss of data on rearrangement of active connections.
The problem with the speedup required to provide non-rearrangeably non-blocking switches through speedup is that the hardware cost to support multicast quickly eliminates any advantage that Space:Time:Space switches or Clos networks provide over switch architectures.
A second approach to providing hardware reduced multicast capability is to use some speedup less than that required for non-rearrangeably non-blocking switches and combine that with a more complicated switch setting algorithm. Under certain cases, the switch setting algorithm can guarantee that no requested connection will ever be rejected. This is known as “wide-sense” non-blocking. These solutions are all inherently rearranging.
Current state of the art for multicast switch architectures is represented by the following public domain publications, each of which is incorporated by reference in its entirety: C. Clos, “A study of non-blocking switching networks”, Bell System Technical Journal, vol. 32, pp. 406-424, March 1953; Y. Yang and G. Masson, “The necessary conditions for Clos-Type nonblocking multicast networks”, IEEE Transactions on Computers, Vol. 48, No. 11, November 1999; U.S. Pat. No. 5,119,368, “High-Speed Time-Division Switching System”, issued on Jun. 2, 1992 to Hiltner et al.; U.S. Pat. No. 5,469,154, “Multiconnection switching networks”, issued on Nov. 21, 1995 to Karp; and J. Hui, Switching and Traffic Theory for Integrated Broadband Networks, Kluwer Academic Publishers, 1990, Chapter 3. pp. 53-84.
Yang and Masson work towards a theoretical bound on speedup required for rearrangably non-blocking multicast in strict Clos networks. They are successful in finding a bound for such networks based on control algorithms where m=cn(log r)/(log log r), where c is “a small constant”. This solution is inherently rearranging.
U.S. Pat. No. 5,119,368 solves the problem of multicast using speedup to create an N×N solution to handle TDM switching of arbitrary grain size. Given n ports of G grains each, the G grains of each port are replicated in space to create n×G inputs to n muxes. Each mux, therefore has the entire input available for selection at each clock tick. No routing algorithm is required since this is essentially an N×N solution.
U.S. Pat. No. 5,469,154 solves the problem using a variation on a 3-stage Clos network with 2× speedup. A simple routing algorithm is presented that while effective has only probabilistic guarantees and no guarantees on running time. For difficult routing problems, the algorithm may require an unbounded amount of time. As well as having no guarantee of success and unbounded running time, this architecture is rearranging.
Multicast is required in TDM data networks for a variety of reasons that can generally be described as data protection and signal distribution. In the case of data protection, this may consist of equipment protection where a vendor wants to provide redundant hardware in the case of the failure of a portion of the equipment. For example, while one line card may suffer a failure or be taken out of service for upgrade or repair, a second redundant line card may then be used to carry the traffic originally on the out-of-service line card. In some cases, the switch to the redundant equipment may be performed automatically based on signal quality. Typically, network operators want as little constraint as possible on protection arrangements. While it may be possible to construct simpler switches using known port placement, such constraints are typically hard to satisfy in the real world with real data connections and service agreements. Network providers typically want the flexibility to multicast data for protection from any port and timeslot to any port and timeslot.
Signal distribution multicast occurs when a single data signal is multicast to several destinations. This can be done when the original data itself is part of richer data connection than typical point-to-point connections, for example a multi-party conference call or the distribution of a video signal to multiple terminals. Typically there is no way to predict where the endpoints of such signal distribution will be. In this case, there is no easy solution other than to provide non-blocking multicast.
The growth of data networking has driven the need for high-capacity data switches. Typically the size of a switching system is limited by the ability to provide switching in a manageable form. Supporting connection rearrangement within a network of switching devices significantly increases the complexity of switch management and typically increases the time needed to respond to connection needs. Although multistage networks theoretically provide a means to create switches of unlimited size, the problem of managing large multistage networks sets a limit on practical size of such networks. Providing non-rearranging high capacity switch components simplifies the creation of such multistage networks and extends the boundary of what may be practically built and managed.
It is, therefore, desirable to provide non-rearrangeably non-blocking multicast with costs reduced from that of n2 switch architectures without introducing expensive switch management algorithms.